package com.arithmetic.basics;

/**
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。
 * <p>
 * 你必须编写一个具有 O(log n) 时间复杂度的算法。
 * 示例 1:
 * <p>
 * 输入: nums = [-1,0,3,5,9,12], target = 9
 * 输出: 4
 * 解释: 9 出现在 nums 中并且下标为 4
 * 示例 2:
 * <p>
 * 输入: nums = [-1,0,3,5,9,12], target = 2
 * 输出: -1
 * 解释: 2 不存在 nums 中因此返回 -1
 * 提示：
 * <p>
 * 你可以假设 nums 中的所有元素是不重复的。
 * n 将在 [1, 10000]之间。
 * nums 的每个元素都将在 [-9999, 9999]之间。
 * Related Topics
 * 数组
 * 二分查找
 * 解题思路
 * 指针l指向-1，r指向nums.length
 * l 代表所有小于target的区间的右端点
 * r 代表所有大于target的区间的左断点
 */
public class Day20 {
    public int search(int[] nums, int target) {
        // 设置指针l和r初始化
        int l = -1, r = nums.length;
        // 二分查找：通过维护两个指针 l 和 r，分别表示小于 target 的区间的右端点和大于 target 的区间的左端点，逐步缩小查找范围，直到找到目标值或确认不存在
        while (l < r - 1) {
            int mid = l + (r - l) / 2;
            // 小于 target 的区间的右端点
            if (nums[mid] < target) {
                l = mid;
                // 大于 target 的区间的左端点
            } else if (nums[mid] > target) {
                r = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }
}
